package com.nanbei.btree;

/**
 * @ClassDescription: B树
 * @JdkVersion: 17
 * @Author: BaoShan.Li
 * @Date: 2024/6/13 22:27
 */
public class BTree {
    BTreeNode root;
    // 树的最小度数
    int t;

    // KEYS 中的最小个数
    final int MIN_KEYS_NUMBER;
    // KEYS 中的最大个数
    final int MAX_KEYS_NUMBER;

    public BTree() {
        this(2);
    }

    public BTree(int t) {
        this.t = t;
        this.root = new BTreeNode(t);
        MIN_KEYS_NUMBER = t - 1;
        MAX_KEYS_NUMBER = 2 * t - 1;
    }

    /**
     * 判断键是否存在
     * @param key 键
     * @return 是否存在
     */
    public boolean contains(int key){
        return root.get(key) != null;
    }

    public void put(int key){
        doPut(root,key,null,0);
    }

    private void doPut(BTreeNode node, int key,BTreeNode parent,int index) {
        int flag = 0;
        while (flag < node.keyNumber) {
            if (node.keys[flag] == key) {
                return;
            }
            if (key < node.keys[flag]) {
                // 找到插入位置
                break;
            }
            flag++;
        }

        if (node.leaf) {
            // 如果当前节点为叶子节点 直接插入
            node.insertKey(key, flag);
        } else {
            // 如果当前节点不是叶子节点，则递归插入叶子节点
            doPut(node.children[flag], key,node,flag);
        }
        // 如果当前节点的key值达到最大容量需要进行分裂
        if(node.keyNumber == MAX_KEYS_NUMBER){
            split(node,parent,index);
        }

    }

    /**
     * 树的分裂
     * @param left 需要进行分裂的节点
     * @param parent 分裂节点的父节点
     * @param index 分裂节点的下标
     */
    public void split(BTreeNode left, BTreeNode parent, int index) {
        if (parent == null) {
            // 分裂的节点为根节点
            BTreeNode newRoot = new BTreeNode(t);
            // 根节点不是叶子节点
            newRoot.leaf = false;
            // 将当前节点插入父节点
            newRoot.insertChildren(left,0);
            this.root = newRoot;
            parent = newRoot;

        }
        // 定义一个新的B树用来存放较大的key
        BTreeNode right = new BTreeNode(t);
        // 新增加的节点和要分裂的节点位置是属于同一层的
        right.leaf = left.leaf;
        //将较大的数值copy到right节点
        System.arraycopy(left.keys, t, right.keys, 0, t - 1);
        if (!left.leaf) {
            // 分裂节点为非叶子节点
            // ps:当前节点的叶子节点在插入数据后进行分裂向上插入一个key后导致key满了，然后进行分裂
            System.arraycopy(left.children, t, right.children, 0, t);
        }
        right.keyNumber = t - 1;
        left.keyNumber = t - 1;
        // 将中间的key插入到数组中
        int key = left.keys[t - 1];
        parent.insertKey(key,index);
        // 将right插入到父节点的子节点数组中
        parent.insertChildren(right, index + 1);
    }

    public void remove(int key){
        doRemove(root,key,null,0);
    }

    private void doRemove(BTreeNode node, int key,BTreeNode parent, int index) {
        int flag = 0;
        while (flag < node.keyNumber) {
            if (node.keys[flag] >= key) {
                break;
            }
            flag++;  // 当flag = node.keyNumber时 证明没有找到要删除的节点，需要向当前节点的最左侧孩子进行查找
        }

        if (node.leaf){
            if (flag < node.keyNumber && node.keys[flag] == key) {   // 是叶子节点，且找到了需要删除的节点
               node.removeKey(flag);
            } else {  // 是叶子节点，但是没有找到要删除的节点
                return;
            }
        }else {
            if (flag < node.keyNumber && node.keys[flag] == key) {  // 不是叶子节点，且找到了需要删除的节点
                BTreeNode successor = node.children[flag+1];
                while (!successor.leaf){
                    successor = successor.children[0];
                }
                // 将后继节点赋值给要删除的节点
                node.keys[flag] = successor.keys[0];
                // 删除后继节点
                doRemove(node.children[flag+1],successor.keys[0],node,flag+1);

            } else { // 不是叶子节点，没有找到需要删除的节点
               doRemove(node.children[flag],key,node,flag);
            }
        }

        if (node.keyNumber < MIN_KEYS_NUMBER){
            // 重新调整平衡
            balance(node,parent,index);
        }


    }

    /**
     * B树删除的调整
     * @param node 需要调整的节点
     * @param parent 需要调整节点的父节点
     * @param index 需要调整节点的下标
     */
    private void balance(BTreeNode node, BTreeNode parent ,int index) {
        if (node == root){ // 当前节点为根节点则不需要调整

            if (root.keyNumber ==0 && root.children[0] != null){
                root = root.children[0];
            }
            return;

        }

        BTreeNode rightSibling = parent.childRightSibling(index);
        BTreeNode leftSibling = parent.childLeftSibling(index);

        // 左边富裕，右旋
        if (leftSibling!=null && leftSibling.keyNumber > MIN_KEYS_NUMBER){
            node.insertKey(parent.keys[index-1],0 );
              // 如果左兄弟或者右兄弟为非叶子节点，那么当前node节点也应该为非叶子节点。
                // 1：为什么会删除一个非叶子节点的值？
                // 2：如果都为非叶子节点，那么node被删除的节点的 左或右 孩子去哪了？
            if (!leftSibling.leaf){ //如果左兄弟不是叶子节点 需要将左兄弟的最右侧孩子挪到node节点的最左侧
                node.insertChildren(leftSibling.removeRightmostChild(),0);
            }
            parent.keys[index-1] = leftSibling.removeRightmostKey();
            return;
        }

        // 右边富裕，左旋
        if (rightSibling!=null && rightSibling.keyNumber > MIN_KEYS_NUMBER){
            node.insertKey(parent.keys[index],node.keyNumber);

            if (!rightSibling.leaf){ //如果右兄弟不是叶子节点 需要将右兄弟的最左侧孩子挪到node节点的最右侧
                node.insertChildren(rightSibling.removeLeftmostChild(),node.keyNumber );
            }

            parent.keys[index]=rightSibling.removeLeftmostKey();
            return;
        }

        if (leftSibling !=null){
            parent.removeChild(index);
            leftSibling.insertKey(parent.removeKey(index-1),leftSibling.keyNumber );
            node.moveToTarget(leftSibling);
            return;
        }
        if (rightSibling != null){
            parent.removeChild(index+1);
            node.insertKey(parent.removeKey(index),node.keyNumber);
            rightSibling.moveToTarget(node);
        }

    }

    public void travel() {
        doTravel(root);
    }

    public void doTravel(BTreeNode node) {
        if (node == null) {
            return;
        }
        int i = 0;
        for (; i < node.keyNumber; i++) {
            doTravel(node.children[i]);
            System.out.println(node.keys[i]);
        }
        doTravel(node.children[i]);
    }


}
